package String;

import java.util.HashMap;
import java.util.Map;

public class _791_CustomSortString {
    //situation consider:when S.length >T.length
    public String customSortString(String S, String T) {
        int length =T.length();
        String rest = "";
        Map<String, Integer> map = new HashMap<>();
        for(int i=0;i<length;i++) {
            String temp = T.charAt(i)+"";
            if (S.contains(temp)) {
                if (map.containsKey(temp)) {
                    map.put(temp, map.get(temp) + 1);
                } else {
                    map.put(temp, 1);
                }
            } else {
                rest+=temp;
            }
        }
        int slength = S.length();
        String result = "";
        for(int i=0;i<slength;i++) {
            String temp = S.charAt(i)+"";
            if (map.get(temp) != null) {
                int count = map.get(temp);
                for (int j = 0; j < count; j ++) {
                    result+=temp;
                }
            }
        }
        result+=rest;
        return result;
    }

    //reference solution,faster,use stringbuffer

    /**
     * first,get every word in T's count,second construct the stringbuffer,finally,add all words which in T but not in S
     * @param S
     * @param T
     * @return
     */
    public String customSortString1(String S, String T) {
        int[] bucket = new int[26];
        StringBuilder sb = new StringBuilder();
        for(char c : T.toCharArray()) {
            bucket[c - 'a'] ++;
        }
        for(char c: S.toCharArray()) {
            for(int i = 0; i < bucket[c - 'a']; i++){
                sb.append(c);
            }
            bucket[c - 'a'] = 0;
        }
        for(int i = 0; i < 26; i++) {
            for(int j = 0; j < bucket[i]; j++) {
                sb.append((char)('a' + i));
            }
        }
        return sb.toString();
    }
}
